import random


class Solution(object):

    def __init__(self, rects):
        """
        :type rects: List[List[int]]
        """
        self.rects = rects
        self.n = len(rects)
        self.nums = [0] * self.n
        self.nums[0] = int((self.rects[0][3] - self.rects[0][1] + 1) * (self.rects[0][2] - self.rects[0][0] + 1))
        for i in range(1, self.n):
            self.nums[i] = self.nums[i - 1] + int((self.rects[i][3] - self.rects[i][1] + 1) * (
                        self.rects[i][2] - self.rects[i][0] + 1))

    def pick(self):
        """
        :rtype: List[int]
        """
        num = random.randint(0, self.nums[-1])
        left = 0
        right = self.n - 1
        while left < right:
            mid = (left + right) // 2
            if self.nums[mid] >= num:
                right = mid
            else:
                left = mid + 1
        rect = self.rects[left]
        x = random.randint(rect[0], rect[2])
        y = random.randint(rect[1], rect[3])
        return [x, y]

